/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
public:
    vector<vector<int>> closestNodes(TreeNode *root, vector<int> &queries)
    {
        vector<int> treeArr;
        inorder(root, treeArr);
        vector<vector<int>> answer;
        for (auto query : queries)
        {
            auto lower = upper_bound(treeArr.begin(), treeArr.end(), query);
            auto upper = lower_bound(treeArr.begin(), treeArr.end(), query);
            int lowerVal = (lower == treeArr.begin()) ? -1 : *(lower - 1);
            int upperVal = (upper == treeArr.end()) ? -1 : *upper;
            answer.push_back({lowerVal, upperVal});
        }
        return answer;
    }

    // 转化成数组再查找
    void inorder(TreeNode *t, vector<int> &v)
    {
        if (t == nullptr)
        {
            return;
        }
        inorder(t->left, v);
        v.push_back(t->val);
        inorder(t->right, v);
    }

    // 直接在树上查找可能会超时
    int nearestNonLess(TreeNode *tree, int n)
    {
        if (tree == nullptr)
        {
            return -1;
        }
        if (tree->val == n)
        {
            return n;
        }
        if (tree->val < n)
        {
            return nearestNonLess(tree->right, n);
        }
        if (tree->val > n)
        {
            if (tree->left == nullptr)
            {
                return tree->val;
            }
            else
            {
                int subNonLess = nearestNonLess(tree->left, n);
                if (subNonLess != -1)
                {
                    return subNonLess;
                }
                else
                {
                    return tree->val;
                }
            }
        }
        return -1;
    }

    int nearestNonGreater(TreeNode *tree, int n)
    {
        if (tree == nullptr)
        {
            return -1;
        }
        if (tree->val == n)
        {
            return n;
        }
        if (tree->val > n)
        {
            return nearestNonGreater(tree->left, n);
        }
        if (tree->val < n)
        {
            if (tree->right == nullptr)
            {
                return tree->val;
            }
            else
            {
                int subNonGreater = nearestNonGreater(tree->right, n);
                if (subNonGreater != -1)
                {
                    return subNonGreater;
                }
                else
                {
                    return tree->val;
                }
            }
        }
        return -1;
    }
};